#1流浪地球
# if __name__ == '__main__':
#     # 信号塔的总个数, 主动变为发射状态的信号塔总个数
#     n, e = map(int, input().split())
#     # 记录每个信号塔的最终变为发射状态时刻, 初始化为极大值，方便后面取最早时刻
#     launches = [float('inf')] * n
#     for _ in range(e):
#         # 信号塔的主动变为发射状态时刻, 信号塔的位置编号
#         t, p = map(int, input().split())
#         # p已在更早时刻被动变为发射状态，因此可以忽略主动变为发射状态时刻
#         if t > launches[p]:
#             continue
#         # 主动变为发射状态：p在t时刻主动变为发射状态
#         launches[p] = t
#         # 被动变为发射状态：q接收到p发射的信号的时间
#         for q in range(n):
#             innerDis = abs(p - q)  # 内传输距离
#             outerDis = n - innerDis  # 外传输距离
#             launches[q] = min(launches[q], launches[p] + min(innerDis, outerDis))
#     last = []
#     lastTime = -1
#     for i in range(n):
#         if launches[i] > lastTime:
#             last.clear()
#             lastTime = launches[i]
#         if launches[i] == lastTime:
#             last.append(i)
#     print(len(last))
#     print(" ".join(map(str, last)))

#2构成正方形的数量
# 输入获取
# n = int(input())
# coordinates = [input() for _ in range(n)]
# # 算法入口
# def getResult():
#     squareCount = 0
#     coordinatesSet = set(coordinates)
#     for i in range(n):
#         x1, y1 = map(int, coordinates[i].split())
#         for j in range(i + 1, n):
#             x2, y2 = map(int, coordinates[j].split())
#             x3 = x1 - (y1 - y2)
#             y3 = y1 + (x1 - x2)
#             x4 = x2 - (y1 - y2)
#             y4 = y2 + (x1 - x2)
#             if f"{x3} {y3}" in coordinatesSet and f"{x4} {y4}" in coordinatesSet:
#                 squareCount += 1
#             x5 = x1 + (y1 - y2)
#             y5 = y1 - (x1 - x2)
#             x6 = x2 + (y1 - y2)
#             y6 = y2 - (x1 - x2)
#             if f"{x5} {y5}" in coordinatesSet and f"{x6} {y6}" in coordinatesSet:
#                 squareCount += 1
#     return squareCount // 4
# # 算法调用
# print(getResult())

#3靠谱的车
# if __name__ == '__main__':
#     nums = input()
#     ans = 0
#     for i in range(len(nums)):
#         num = int(nums[i])
#         if num > 4:
#             num -= 1  # 若十进制对应位值大于4，则需要减去1后作为九进制对应位值
#         ans += num * (9 ** (len(nums) - 1 - i))  # nums 的第 nums.length-1 位对应九进制的第 0 位
#     print(ans)

#4敏感字段加密
# 输入获取
# k = int(input())
# s = input()
# # 算法入口
# def solution():
#     global s
#     commands = []
#     # 双引号是否处于开启状态
#     isQuotaOpen = False
#     # 避免收尾操作, s 尾部追加一个 '_' 不影响结果
#     s += "_"
#     command = []
#     for c in s:
#         # 如果遇到双引号, 则先将 isQuotaOpen 取反
#         if c == '"':
#             isQuotaOpen = not isQuotaOpen
#         if c != '_' or isQuotaOpen:
#             # 如果遇到的 c 不是 '_' 或者是双引号里面的 '_', 则此时 c 不是命令字分隔符, 而是命令字一部分
#             command.append(c)
#         elif len(command) > 0:
#             # 如果 c 是命令字分隔符, 且 command 命令字不为空, 则命令字被截断
#             commands.append("".join(command))
#             # 清空command, 用于下个命令字的收集
#             command.clear()
#     if k >= len(commands):
#         # 如果无法找到指定索引的命令字，输出字符串ERROR
#         return "ERROR"
#     else:
#         # 对指定索引的敏感字段进行加密，替换为******（6个*），并删除命令字前后多余的下划线_
#         commands[k] = "******"
#         return "_".join(commands)
# # 算法调用
# print(solution())

#5TVL解码
# if __name__ == '__main__':
#     target = input()
#     stream = input().split()
#     i = 0
#     while i < len(stream):
#         tag = stream[i]
#         length = int(stream[i + 2] + stream[i + 1], 16)
#         i += 3
#         if tag == target:
#             print(" ".join(stream[i:i + length]))
#             break
#         i += length

#6分披萨
# 输入获取
# n = int(input())  # 披萨数量（奇数个）
# pizza = []  # n个披萨的大小（各不相同）
# for _ in range(n):
#     pizza.append(int(input()))
# # 缓存表
# cache = [[0] * n for _ in range(n)]
# # 越界索引环形变化
# def check(idx):
#     if idx < 0:
#         idx = n - 1
#     elif idx >= n:
#         idx = 0
#     return idx
# def recursive(l, r):
#     # 进入递归前，"吃货"已经拿了披萨，因此进入递归后，轮到"馋嘴"拿
#     # 而"馋嘴"拿披萨的策略固定是：缺口左右两边中较大的那块
#     if pizza[l] > pizza[r]:  # 注意披萨大小各部相同，因此要么左边大，要么右边大，不存在相等的情况
#         # 拿走第 l 块，因此缺口左边的位置变为 l - 1
#         l = check(l - 1)
#     else:
#         # 拿走第 r 块，因此缺口右边的位置变为 r + 1
#         r = check(r + 1)
#
#     if cache[l][r] > 0:
#         return cache[l][r]
#     if l == r:
#         # 当 l == r 是，说明只剩一块披萨了，由于奇数个披萨，且"吃货"第一个拿，因此最后一个也是"吃货"拿
#         cache[l][r] = pizza[l]
#     else:
#         # 如果还剩多块披萨，那么"吃货"有两种选择：
#         # 1、拿缺口左边的披萨
#         # 2、拿缺口右边的披萨
#         # 因此这里直接开两个递归分支，最终结果取较大值
#         cache[l][r] = max(recursive(check(l - 1), r) + pizza[l], recursive(l, check(r + 1)) + pizza[r])
#     return cache[l][r]
# def getResult():
#     # ans记录"吃货"能获得的最大披萨大小
#     ans = 0
#     # i 指向首轮被"吃货"选取的披萨位置，可以理解为缺口位置，相当于给环切了一个口
#     for i in range(n):
#         # i - 1 是缺口的左边披萨，check函数作用是防止 i - 1 越界, 进行绕环运动
#         # i + 1 是缺口的右边披萨，check函数作用是防止 i + 1 越界，进行绕环运动
#         # recursive的作用求解是"吃货"从缺失了 第 i 块的披萨铁盘 开始选，最终可得的最大披萨大小，
#         # 而第 i 块是首轮就被"吃货"拿走的，因此是recursive + pizza[i]
#         ans = max(ans, recursive(check(i - 1), check(i + 1)) + pizza[i])
#     return ans
# print(getResult())

#7 boss的收入
# n = int(input())
#
# # income: 记录每个代理商赚的钱, key是代理商号, val是代理商赚的钱
# income = {}
# # agents: 记录所有的代理商号
# agents = set()
# # ch_fa: key是子级代理商号, val是父级代理商号
# ch_fa = {}
# # fa_ch: key是父级代理上号, val是key的所有子级代理商号
# fa_ch = {}
# for _ in range(n):
#     # 子级代理商号,父级代理商号,子级代理商号赚的钱
#     ch_id, fa_id, ch_income = input().split()
#     income[ch_id] = int(ch_income)
#     agents.add(ch_id)
#     agents.add(fa_id)
#     ch_fa[ch_id] = fa_id
#     fa_ch.setdefault(fa_id, [])
#     fa_ch.setdefault(ch_id, [])
#     fa_ch[fa_id].append(ch_id)
#
# # 基于递归的深搜
# def dfs(fa):
#     # 父级代理商号的所有子级代理商号chs
#     chs = fa_ch[fa]
#
#     # 如果存在子级代理商, 则父级代理商从每一个子级代理商赚的钱中：每100元抽15元
#     if len(chs) > 0:
#         for ch in chs:
#             dfs(ch)
#             income[fa] += income[ch] // 100 * 15
# # 算法入口
# def getResult():
#     for agent in agents:
#         # 顶级代理商号（根）没有父级
#         if ch_fa.get(agent) is None:
#             # 设置顶级代理商号 初始金额 为0
#             income[agent] = 0
#             # 开始深搜
#             dfs(agent)
#             return f"{agent} {income[agent]}"
# # 算法调用
# print(getResult())

#8 手机app防沉迷系统
# class App:
#     def __init__(self,name,pri,start,end):
#         self.name = name
#         self.pri = pri
#         self.start = start
#         self.end = end
#
# def convert(time):
#     hour,minute = map(int,time.split(":"))
#     return hour * 60 +minute
# apps = []
#
# n = int(input())
# for _ in range(n):
#     name,pri,start,end = input().split()
#     apps.append(App(name,int(pri),convert(start),convert(end)))
#
# queryTime = convert(input())
#
# def getRes():
#     registereds = []
#     for app in apps:
#         if app.start > app.end: #开始时间大于结束时间
#             continue
#         idxs = []
#         flag = False
#         for j in range(len(registereds)):
#             registered = registereds[j]
#             if registered.start >= app.end or registered.end < app.start: #注册时间无冲突
#                 continue
#             if app.pri > registered.pri: #新注册优先级高
#                 idxs.append(j)
#             else:
#                 flag = True
#                 break
#         if flag:
#             continue
#         idxs.reverse()
#         for idx in idxs:
#             registereds.pop(idx)
#         registereds.append(app)
#     ans = "NA"
#     for registered in registereds:
#         if registered.start <= queryTime < registered.end:
#             ans = registered.name
#             break
#     return ans
# print(getRes())

#9字符串分割
# n = int(input())
# string = input()
# arr = string.split('-')
# tmp = ''.join(arr[1:])
# res = []
# res.append(arr[0])
# for i in range(0,len(tmp),n):
#     substr = tmp[i:i+n]
#     upcnt = 0
#     lwcnt = 0
#     for c in substr:
#         if 'z' >= c >= 'a':
#             lwcnt += 1
#         if 'Z' >= c >= 'A':
#             upcnt += 1
#     if lwcnt > upcnt:
#         substr = substr.lower()
#     elif upcnt > lwcnt:
#         substr = substr.upper()
#     res.append(substr)
# print('-'.join(res))

#10# #英文输入法
# import re
# word = input()
# pre = input()
# ret = []
# tmp = re.split('[^a-zA-Z]',word)
# cache = list(set(tmp))
# for s in cache:
#     if s.startswith(pre):
#         ret.append(s)
# if len(ret) > 0:
#     print(' '.join(ret))
# else:
#     print(pre)

#11连续字母长度
# k = int(input())
# s = input() + '0'
# count = {}
# i = 0
# for j in range(1,len(s)):
#     if s[j] != s[i]:
#         count[s[i]] = max(count.get(s[i],0),j-i)
#         i = j
# print(sorted(count.values(),reverse=True)[k-1])
# alphet = [0] * 26
# start = s[0]
# alphet[ord(start)- ord('A')] = 1
# pre = start
# cnt = 1
# for i in range(1, len(s)):
#     # print(cnt)
#     if s[i] == pre:
#         pre = s[i]
#         cnt += 1
#     else:
#         if cnt > alphet[ord(pre) - ord('A')]:
#             alphet[ord(pre) - ord('A')] = cnt
#         cnt = 1
#         pre = s[i]
# alphet.sort(reverse=True)
# if k < 1 or k > 26:
#     print(-1)
#     exit()
# else:
#     print(alphet[k-1] if alphet[k-1] > 0 else -1)

#12考勤系统算法
# n = int(input())
# records = [input().split() for _ in range(n)]
# leavelate = ['leaveearly','late']
#
# def isAward(record):
#     preRecord = ''
#     absent = 0
#     present = 0
#     for i in range(len(record)):
#         if i >= 7:
#             if record[i-7] == 'present':
#                 present -= 1
#         curRecord = record[i]
#
#         if curRecord == 'absent':
#             absent += 1
#             if absent > 1:
#                 return "false"
#         elif curRecord in leavelate and preRecord in leavelate:
#             return "false"
#         elif curRecord == 'present':
#             present += 1
#         preRecord = curRecord
#         window_length = min(i+1,7)
#         if window_length - present > 3:
#             return "false"
#     return "true"
#
# for record in records:
#     print(isAward(record))

#13#字符串变换算法
# def getRes():
#     s= input()
#     minArr = list(s)
#     minArr.sort()
#     if s == ''.join(minArr):
#         return s
#     curArr = list(s)
#     # print(curArr.index('d'))
#     for i in range(len(minArr)):
#         if curArr[i] != minArr[i]:
#             tmp = curArr[i]
#             swapIdx = curArr.index(minArr[i])
#             curArr[i] = minArr[i]
#             print(swapIdx)
#             curArr[swapIdx] = tmp
#             break
#     return "".join(curArr)
#
# print(getRes())


#14整数对最小和
# arr1 = list(map(int,input().split()))
# arr2 = list(map(int,input().split()))
# k = int(input())
# len1 = arr1[0]
# arr1 = arr1[1:]
# print(arr1)
# len2 = arr2[0]
# arr2 = arr2[1:]
# sum = []
# for i in range(len1):
#     for j in range(len2):
#         sum.append(arr1[i]+arr2[j])
# sum.sort()
# ret = 0
# for i in range(k):
#     ret += sum[i]
# print(ret)

#15智能成绩表
# class Student:
#     def __init__(self,name,rank):
#         self.name = name
#         self.rank = rank
# n,m = map(int,input().split())
# subject = input().split()
# subject_rankIdx = {}
# for i in range(m):
#     subject_rankIdx[subject[i]] = i
# students = []
# for i in range(n):
#     tmp = input().split()
#     name = tmp[0]
#     scores = list(map(int,tmp[1:]))
#
#     rank = []
#     rank.extend(scores)
#     rank.append(sum(scores))
#
#     students.append(Student(name,rank))
#
# find = input()
# rankIdx = subject_rankIdx.get(find,m)
# students.sort(key = lambda x: (-x.rank[rankIdx],x.name))
# # students.sort(key = -students.rank[rankIdx])
# ret = []
# for i in range(len(students)):
#     ret.append(students[i].name)
# print(' '.join(ret))
# # print(''.join(map(lambda x:x.name,students)))

# 16计算面积
# N,E = map(int,input().split())
# ans = 0
# x = 0
# y = 0
# for _ in range(N):
#     num,offset = map(int,input().split())
#     ans += (num - x) * abs(y + offset)
#     x,y = num, y+ offset
# if E > x: #结束位置
#     ans+=(E - x) * abs(y)

#17响应报文时间
# def Timeresponse(m):
#     if m >= 128:
#         bStr = bin(m)
#         print(bStr)
#         bStr = bin(m)[2:]
#         print(bStr)
#
#         exp = int(bStr[1:4],2)
#         mant = int(bStr[4:],2)
#         return ( mant | 16) << (exp+3)
#     else:
#         return m

#18跳房子1
# steps = list(map(int,input()[1:-1].split(',')))
# count = int(input())
# print(steps)
#
# dic = {}
# minIdxSum = sys.maxsize
# ans = ''
# for idx in range(len(steps)):
#     step1 = steps[idx]
#     step2 = count - step1
#     if dic.get(step2) is None:
#         # dic.setdefault(step1,idx)
#         dic[step1] = idx
#     else:
#         idxx = dic[step2]
#         idxSum = idx + idxx
#         if idxSum < minIdxSum:
#             minIdxSum = idxSum
#             ans = f"[{step2} {step1}]"
# print(ans)

#19字符串模糊匹配
# def getRes():
#     src = input()
#     tar = input()
#     levels = []
#     level = set()
#     isOpen = False
#
#     for c in tar:
#         if c == '[':
#             isOpen = True
#         elif c == ']':
#             isOpen = False
#             levels.append(level)
#             level = set()
#         elif isOpen:
#             level.add(c)
#         else:
#             levels.append({c})
#     print(levels)
#     for i in range(len(src)-len(levels)+1):
#         j = 0
#         while j < len(levels):
#             if src[i+j] not in levels[j]:
#                 break
#             j+=1
#         if j == len(levels):
#             return i
#     return -1
#
# print(getRes())

#20投资策略优化
# class Product:
#     def __init__(self,rate,risk,asset):
#         Product.rate = rate
#         Product.risk = risk
#         Product.asset = asset
# n,money,max_risk = map(int,input().split())
# rate = list(map(int,input().split()))
# risk = list(map(int,input().split()))
# asset = list(map(int,input().split()))
# rate_sum = 0
# risk_sum = 0
# asset_sum = 0
# max_profit = 0
# idx = []
# for i in range(n):
#     if risk[i] <= max_risk:
#         if asset[i] <= money:
#             if asset[i] * rate[i]  > max_profit:
#                 max_profit = asset[i] * rate[i]
#                 idx = [0 for _ in range(n)]
#                 idx[i] = asset[i]
#         else:
#             if money  * rate[i]  > max_profit:
#                 max_profit = money * rate[i]
#                 idx = [0 for _ in range(n)]
#                 idx[i] = money
# # print(idx)
# for i in range(n-1):
#     for j in range(i+1,n):
#         if risk[i]+risk[j] <= max_risk:
#             if asset[i] + asset[j] <= money:
#                 if asset[i] * rate[i] + asset[j] * rate[j] > max_profit:
#                     max_profit = asset[i] * rate[i] + asset[j] * rate[j]
#                     idx = [0 for _ in range(n)]
#                     idx[i] = asset[i]
#                     idx[j] = asset[j]
#             else:
#                 if asset[i] * rate[i] + (money- asset[i]) * rate[j] > max_profit:
#                     max_profit = asset[i] * rate[i] + (money- asset[i]) * rate[j]
#                     idx = [0 for _ in range(n)]
#                     idx[i] = asset[i]
#                     idx[j] = money - asset[i]
#                 if asset[j] * rate[j] + (money- asset[j]) * rate[i] > max_profit:
#                     max_profit = asset[j] * rate[j] + (money- asset[j]) * rate[i]
#                     idx = [0 for _ in range(n)]
#                     idx[j] = asset[j]
#                     idx[i] = money - asset[j]
#
# print(' '.join(map(str,idx)))

#21三茶树高度
# class TreeNode:
#     def __init__(self,val):
#         self.val = val
#         self.height = None
#         self.left = None
#         self.right = None
#         self.mid = None
# class Tree:
#     def __init__(self):
#         self.root = None #树的根结点
#         self.height = 0 #树的高度
#
#     def add(self,val):
#         node = TreeNode(val)
#
#         if self.root is None:
#             #树为空，当前创建结点为根结点
#             node.height = 1 #根结点高度为1
#             self.root = node
#             self.height = 1
#         else:
#             #树非空 则从根结点开始比较
#             cur = self.root
#
#             while True:
#                 node.height = cur.height + 1
#                 self.height = max(node.height, self.height)
#
#                 if val < cur.val - 500:
#                     if cur.left is None:
#                         cur.left = node
#                         break
#                     else:
#                         cur = cur.left
#                 elif val > cur.val + 500:
#                     if cur.right is None:
#                         cur.right = node
#                         break
#                     else:
#                         cur = cur.right
#                 else:
#                     if cur.mid is None:
#                         cur.mid = node
#                         break
#                     else:
#                         cur = cur.mid
#
# n = int(input())
# tree = Tree()
# for i in range(n):
#     num = int(input())
#     tree.add(num)
# print(tree.height)


#22数组拼接
# cnt = int(input())
# str_cnt = int(input())
# lists = [list(filter(lambda x : x != '',input().split(','))) for _ in range(str_cnt)]
# print(lists)
# # str_arr = []
# # for _ in range(str_cnt):
# #     s = list(input().split(','))
# #     s2 = [x for x in s if x != '']
# #     str_arr.append(s2)
# # print(str_arr)
# ans = []
# while len(lists) > 0:
#     lst = lists.pop(0)
#     tmp = lst[:cnt]
#     del lst[:cnt]
#     ans.extend(tmp)
#     if len(lst)>0:
#         lists.append(lst)
#
# print(','.join(ans))

#24分糖果
# def rec(n,count):
#     if n == 1:
#         return count
#     if n % 2 == 0:
#         # count +=1
#         return rec(n/2,count+1)
#     else:
#         return min(rec(n+1,count+1),rec(n-1 ,count+1))
#
# num = int(input())
# print(rec(num,0))

#25判断一组不等式组
# lists = list(map(lambda x:x.split(","),input().split(':')))
#
# a11,a12,a13,a14,a15 = map(float,lists[0])

#26高矮个子排序
# try:
#     nums = list(map(int,input().split()))
#     for i in range(len(nums)-1):
#         needSwap = False
#         if i % 2 == 0:
#             if nums[i] < nums[i+1]:
#                 needSwap = True
#         else:
#             if nums[i] > nums[i+1]:
#                 needSwap = True
#         if needSwap:
#             nums[i],nums[i+1] = nums[i+1], nums[i]
#
#     print(" ".join(map(str,nums)))
# except ValueError:
#     print("[]")

#27喊7的次数重排
# 输入获取
# arr = list(map(int, input().split()))
# # 算法入口
# def getResult():
#     # totalGo表示一共喊了多少次过
#     totalGo = sum(arr)
#     # n表示一共几个人
#     n = len(arr)
#     # p[i]表示每个人喊了几次过，初始为0
#     p = [0] * n
#     i = 1  # i 记录喊的数字
#     j = 0  # j 记录第几个人喊
#     while totalGo > 0:
#         # 遇到7, 喊过
#         if i % 7 == 0 or str(i).find("7") != -1:
#             totalGo -= 1
#             p[j] += 1
#         i += 1  # 下一个人喊的数字+1
#         j += 1
#         if j >= n:  # 回到第一个人继续喊
#             j = 0
#     return " ".join(map(str, p))
# # 算法调用
# print(getResult())


#28 补种未成活胡杨
# 输入获取
# n = int(input())
# m = int(input())
# empty = list(map(int, input().split()))
# k = int(input())
# # 算法入口
# def getResult():
#     # 如果空位数量m 等于 新同学数量 k，则可以坐满一排，即最长连续学生数为 n
#     if m == k:
#         return n
#     # 下面逻辑请看题目解析推导过程
#     maxLen = 0
#     for i in range(m - k + 1):
#         if i == 0:
#             maxLen = max(maxLen, empty[i + k] - 1)
#         elif i == m - k:
#             maxLen = max(maxLen, n - empty[i - 1])
#         else:
#             maxLen = max(maxLen, empty[i + k] - empty[i - 1] - 1)
#     return maxLen
# # 算法调用
# print(getResult())

#29矩形相交面积
# 输入获取
# x1, y1, w1, h1 = map(int, input().split())
# x2, y2, w2, h2 = map(int, input().split())
# x3, y3, w3, h3 = map(int, input().split())
# # 算法入口
# def getResult():
#     wid = min(x1 + w1, x2 + w2, x3 + w3) - max(x1, x2, x3)
#     hei = min(y1, y2, y3) - max(y1 - h1, y2 - h2, y3 - h3)
#     return max(0, wid) * max(0, hei)
# # 调用算法
# print(getResult())

#30数大雁
# 输入获取
# quacks = input()
# def getResult():
#     q = []
#     u, a, c = 0, 0, 0
#     rans = []
#     for i in range(len(quacks)):
#         char = quacks[i]
#         if char == 'q':
#             q.append(i)
#         elif char == 'u':
#             if u + 1 <= len(q):
#                 u += 1
#         elif char == 'a':
#             if a + 1 <= u:
#                 a += 1
#         elif char == 'c':
#             if c + 1 <= a:
#                 c += 1
#         elif char == 'k':
#             if c >= 1:
#                 rans.append([q.pop(0), i])
#                 u -= 1
#                 a -= 1
#                 c -= 1
#         else:
#             return -1
#     if len(rans) == 0:
#         return -1
#     ans = 1
#     for i in range(len(rans)):
#         count = 1
#         for j in range(i + 1, len(rans)):
#             if rans[i][1] >= rans[j][0]:
#                 count += 1
#         ans = max(ans, count)
#     return ans

#30#日志采集系统
# log = list(map(int,input().split()))
# n = len(log)
# dp = [0] * n
# delay = [0] * n
# dp[0] = log[0]
# delay[0] = 0
# max_score = dp[0] - delay[0]
# for i in range(1,n):
#     dp[i] =  min(100, dp[i-1] + log[i])
#     delay[i] = delay[i-1] + dp[i-1]
#     max_score = max(max_score,dp[i] - delay[i])
#     if dp[i] == 100:
#         break
# print(max_score)

#31分苹果
# 输入获取
# n = int(input())
# weights = list(map(int, input().split()))
# # 算法入口
# def getResult():
#     weights.sort()
#     fault = weights[0]
#     correct = weights[0]
#     for i in range(1, n):
#         fault ^= weights[i]
#         correct += weights[i]
#     if fault == 0:
#         return correct - weights[0]
#     else:
#         return -1

#32内存资源分配
# 输入获取
# memories = list(map(lambda x: list(map(int, x.split(":"))), input().split(",")))
# requests = list(map(int, filter(lambda x: x != "", input().split(","))))
# # 二分查找
# def binarySearch(arr, key):
#     l = 0
#     r = len(arr) - 1
#     while l <= r:
#         mid = (l + r) // 2
#         midVal = arr[mid][0]
#
#         if midVal > key:
#             r = mid - 1
#         elif midVal < key:
#             l = mid + 1
#         else:
#             return mid
#     return l
# # 算法入口
# def getResult():
#     # 按照内存粒度大小升序
#     memories.sort(key=lambda x: x[0])
#     # 记录结果
#     res = []
#     # 遍历申请列表
#     for req in requests:
#         # 二分查找（找到大于等于request的内存资源）
#         i = binarySearch(memories, req)
#
#         if i < len(memories):
#             # 如果找到>=申请大小的内存池资源
#             res.append("true")
#
#             # 移除数量为0的内存池资源
#             memories[i][1] -= 1
#             if memories[i][1] == 0:
#                 memories.pop(i)
#         else:
#             # 如果找不到
#             res.append("false")
#
#     return ",".join(res)

#33#找终点
# minstep = sys.maxsize
# arr = list(map(int,input().split()))
# for i in range(1,len(arr)//2):
#     j = i + arr[i]
#     step = 2
#     while j < len(arr)-1:
#         j += arr[j]
#         step += 1
#     if j == len(arr) - 1:
#         minstep = min(minstep,step)
#         break
# print(minstep)

#34斗地主之顺子
# 输入获取
# cards = input().split()
# 将牌面映射为数字
# def card2Num(card):
#     if card == "J":
#         return 11
#     elif card == "Q":
#         return 12
#     elif card == "K":
#         return 13
#     elif card == "A":
#         return 14
#     elif card == "2":
#         return 16
#     else:
#         return int(card)

# def getResult():
#     # 牌大小升序
#     cards.sort(key=lambda x: card2Num(x))
#     # 记录顺子
#     straights = []
#     for card in cards:
#         j = 0
#         while j < len(straights):
#             if card2Num(card) - card2Num(straights[j][-1]) == 1:
#                 # 如果card牌面比顺子最后一张牌面大1，则可以拼接到该顺子尾部
#                 straights[j].append(card)
#                 break
#             j += 1
#         # 如果card无法拼接到已有顺子的尾部, 则重新建立一个顺子, 该顺子以card开头
#         if j == len(straights):
#             straights.append([card])
#     # 过滤出符合要求（牌数量>=5）的顺子
#     straights = list(filter(lambda x: len(x) >= 5, straights))
#     if len(straights) == 0:
#         # 如果没有满足出牌规则的顺子，请输出No
#         return "No"
#     else:
#         return "\n".join(map(lambda straight: " ".join(straight), straights))


#35_哈夫曼树
# import heapq
# class Node:
#     def __init__(self,lc,rc,weight,height):
#         self.lc = lc
#         self.rc = rc
#         self.weight = weight
#         self.height = height
#     def __gt__(self, other):
#         #权重小的优先级高， 权重相同时高度小的优先级高
#         if self.weight != other.weight:
#             return  self.weight > other.weight
#         else:
#             return self.height > other.weight
# n = int(input())
# weights = list(map(int,input().split()))
#
# def midOrder(root,seq):
#     if root.lc is not None:
#         midOrder(root.lc,seq)
#     seq.append(root.weight)
#
#     if root.rc is not None:
#         midOrder(root.rc,seq)
#
# pq = []
# for w in weights:
#     #创建n个哈夫曼树结点，并加入优先队列
#     heapq.heappush(pq,Node(None,None,w,0))
#
# while len(pq) > 1:
#     lc = heapq.heappop(pq)
#     rc = heapq.heappop(pq)
#     print(lc.weight,rc.weight)
#     fa_weight = lc.weight + rc.weight
#     fa_height = max(lc.height, rc.height) + 1
#     heapq.heappush(pq,Node(lc,rc,fa_weight,fa_height))
# root = heapq.heappop(pq)
# seq = []
# midOrder(root,seq)
# print(' '.join(map(str,seq)))
import functools
import heapq
import math
import sys

#36最长连续子序列
# nums = list(map(int,input().split(',')))
# tar = int(input())
# n = len(nums)
# pre = [0] * n
# for i in range(1,n+1):
#     pre[i] = pre[i-1] + nums[i-1]
# maxlen = -1
#
# for l in range(1,n+1):
#     for r in range(l,n+1):
#         if pre[r] - pre[l] == tar:
#             maxlen = max(maxlen,r-l+1)
# print(maxlen)

#37压缩字符串解压
# s = input()
# n = len(s)
# i = 0
# ans = ''
# cnt = 0
# while i < n:
#     if 'a' <= s[i] <= 'z' or '0' <= s[i] <= '9':
#         if '0' <= s[i] <= '9':
#             cnt =  cnt * 10 + int(s[i])
#             i += 1
#             continue
#         else:
#             if cnt > 2:
#                 ans += s[i] * cnt
#                 cnt = 0
#             else:
#                 ans += s[i]
#             i += 1
#     else:
#         print('!error')
#         exit()
#
# ans += " "
# m = len(ans)
# i = 1
# ans_back = ''
#
# cnt = 1
# pre = ans[0]
# while i < m:
#     if ans[i] == ans[i-1]:
#         cnt+=1
#     else:
#         if cnt > 2:
#             ans_back += str(cnt)
#             ans_back += pre
#         else:
#             ans_back += pre * cnt
#         cnt = 1
#     pre = ans[i]
#     i+=1
# print(ans,ans_back)

#38最小的调整次数
# n = int(input())
# cmds = [input() for _ in range(2*n)]
# size = 0
# isSorted = False
# count = 0
# for cmd in cmds:
#     if cmd.startswith('head add'):
#         if size == 0:
#             isSorted = True
#         else:
#             isSorted = False
#         size += 1
#     elif cmd.startswith('tail add'):
#         size += 1
#
#     else:
#         if size == 0:
#             continue
#         if  not isSorted:
#             count+=1
#             isSorted = True
#         size -= 1
# print(count)